/*
 * Copyright (C) 2010 Jens Bierschenk
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.googlecode.algorithmlaboratory.redblacktree;

import java.util.Collection;

import com.googlecode.algorithmlaboratory.AbstractTree;

public class RedBlackTree<E extends Comparable<E>> extends AbstractTree<E> {
	
	private static final boolean RED = true;
	private static final boolean BLACK = false;
	
	/**
	 * Constructs a new, empty set, sorted according to the elements natural order.
	 */
	public RedBlackTree() {
		super();
	}
	
	/**
	 * Constructs a new, insert with the elements of the collection, sorted according to the elements natural order.
	 * @param collection of elements, that should be insert
	 */
	public RedBlackTree(Collection<E> collection){
		super(collection);
	}

	/**
	 * Adds the specified element to this red-black tree if it is not already present. If this set already contains the element, 
	 * the call leaves the set unchanged and returns false.
	 * @param value element to be added to this set
	 * @return {@code true} if this set did not already contain the specified element 
	 * @throws NullPointerException - if the specified element is null
	 */
	@Override public boolean add(E value) {
		if(value == null){
			throw new NullPointerException( "The specified parameter is null." );
		
		}else if(root == null){
			root = new RedBlackTreeNode<E>(null, value, BLACK);
		}else{
			RedBlackTreeNode<E> parent = null;
			RedBlackTreeNode<E> child = (RedBlackTreeNode<E>) root;
			
			while(child != null){
				int cmp = child.getValue().compareTo(value);
				if(cmp == 0){
					return false;
				}else{
					parent = child;
					child = (RedBlackTreeNode<E>) (cmp > 0 ? child.getLeftNode() : child.getRightNode());
				}
			}
			
			RedBlackTreeNode<E> node = new RedBlackTreeNode<E>(parent, value, RED);
			if(parent.getValue().compareTo(value) > 0){
				parent.setLeftNode(node);
			}else{
				parent.setRightNode(node);
			}
			fixAfterInsertion(node);
		}
		size++;
		return true;
	}

	/**
	 * Removes the specified element from this red-black tree if it is present. Returns {@code true} if the specified element removed.
	 * @param object to be removed from this red-black tree, if present
	 * @return {@code true} if the specified element removed
	 * @return {@code false} if the specified element not removed
	 * @throws NullPointerException if the specified element is null
	 * @throws ClassCastException if the specified object cannot be compared with the elements currently in the red-black tree
	 */
	@SuppressWarnings("unchecked")
	@Override public boolean remove(Object object) {
		RedBlackTreeNode<E> p = (RedBlackTreeNode<E>) findNode((E) object);
		
		if(p != null){
			if(leftOf(p) != null && rightOf(p) != null){
				RedBlackTreeNode<E> s = (RedBlackTreeNode<E>) successor(p);
				p.setValue(s.getValue());
				p = s;
			}
			
			RedBlackTreeNode<E> replacement = leftOf(p) != null ? leftOf(p) : rightOf(p);
			if(replacement != null){
				replacement.setParentNode(parentOf(p));
				
				if(parentOf(p) == null){
					root = replacement;
				}else if(p == leftOf(parentOf(p))){
					parentOf(p).setLeftNode(replacement);
				}else{
					parentOf(p).setRightNode(replacement);
				}
				p.setLeftNode(null);
				p.setRightNode(null);
				p.setParentNode(null);
				
				if(colorOf(p) == BLACK){
					fixAfterDeletion(replacement);
				}
			}else if(parentOf(p) == null){
				root = null;
			}else{
				if(colorOf(p) == BLACK){
					fixAfterDeletion(p);
				}
				
				if(parentOf(p) != null){
					if(p == leftOf(parentOf(p))){
						parentOf(p).setLeftNode(null);
					}else{
						parentOf(p).setRightNode(null);
					}
					p.setParentNode(null);
				}
			}
			size--;
			return true;
		}else{
			return false;
		}
	}
	
	private void fixAfterDeletion(RedBlackTreeNode<E> x) {
		while(x != root && colorOf(x) == BLACK){
			if(x == leftOf(parentOf(x))){
				RedBlackTreeNode<E> w = rightOf(parentOf(x));
				
				if(colorOf(w) == RED){
					w.setNodeColor(BLACK);
					parentOf(w).setNodeColor(RED);
					rotateLeft(parentOf(x));
					w = rightOf(parentOf(x));
				}
				if(colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK){
					w.setNodeColor(RED);
					x = parentOf(x);
				}else{
					if(colorOf(rightOf(w)) == BLACK){
						leftOf(w).setNodeColor(BLACK);
						w.setNodeColor(RED);
						rotateRight(w);
						w = rightOf(parentOf(x));
					}
					w.setNodeColor(colorOf(parentOf(x)));
					parentOf(x).setNodeColor(BLACK);
					rightOf(w).setNodeColor(BLACK);
					rotateLeft(parentOf(x));
					x = (RedBlackTreeNode<E>) root;
				}
			}else{
				RedBlackTreeNode<E> w = leftOf(parentOf(x));
				
				if(colorOf(w) == RED){
					w.setNodeColor(BLACK);
					parentOf(w).setNodeColor(RED);
					rotateRight(parentOf(x));
					w = leftOf(parentOf(x));
				}
				if(colorOf(rightOf(w)) == BLACK && colorOf(leftOf(w)) == BLACK){
					w.setNodeColor(RED);
					x = parentOf(x);
				}else{
					if(colorOf(leftOf(w)) == BLACK){
						rightOf(w).setNodeColor(BLACK);
						w.setNodeColor(RED);
						rotateLeft(w);
						w = leftOf(parentOf(x));
					}
					w.setNodeColor(colorOf(parentOf(x)));
					parentOf(x).setNodeColor(BLACK);
					leftOf(w).setNodeColor(BLACK);
					rotateRight(parentOf(x));
					x = (RedBlackTreeNode<E>) root;
				}
			}
		}
		x.setNodeColor(BLACK);
	}

	private void fixAfterInsertion(RedBlackTreeNode<E> z) {
		while(z != null && z != root && colorOf(parentOf(z)) == RED) {
			if(parentOf(z) == leftOf(parentOf(parentOf(z)))) {
				RedBlackTreeNode<E> y = rightOf(parentOf(parentOf(z)));
				
				if(colorOf(y) == RED){
					parentOf(z).setNodeColor(BLACK);
					y.setNodeColor(BLACK);
					parentOf(parentOf(z)).setNodeColor(RED);
					z = parentOf(parentOf(z));
				}else{
					if(z == rightOf(parentOf(z))){
						z = parentOf(z);
						rotateLeft(z);
					}
					parentOf(z).setNodeColor(BLACK);
					parentOf(parentOf(z)).setNodeColor(RED);
					rotateRight(parentOf(parentOf(z)));
				}
			}else{
				RedBlackTreeNode<E> y = leftOf(parentOf(parentOf(z)));
				
				if(colorOf(y) == RED){
					parentOf(z).setNodeColor(BLACK);
					y.setNodeColor(BLACK);
					parentOf(parentOf(z)).setNodeColor(RED);
					z = parentOf(parentOf(z));
				}else{
					if(z == leftOf(parentOf(z))){
						z = parentOf(z);
						rotateRight(z);
					}
					parentOf(z).setNodeColor(BLACK);
					parentOf(parentOf(z)).setNodeColor(RED);
					rotateLeft(parentOf(parentOf(z)));
				}
			}
		}
		((RedBlackTreeNode<E>) root).setNodeColor(BLACK);
	}
	
	private void rotateLeft(RedBlackTreeNode<E> node){
		if(node != null){
			RedBlackTreeNode<E> lowerNode = (RedBlackTreeNode<E>) node.getRightNode();
			node.setRightNode(lowerNode.getLeftNode());
			
			if(lowerNode.getLeftNode() != null){
				lowerNode.getLeftNode().setParentNode(node);
			}
			lowerNode.setParentNode(node.getParentNode());
			
			if(node.getParentNode() == null){
				root = lowerNode;
			}else if(node == node.getParentNode().getLeftNode()){
				node.getParentNode().setLeftNode(lowerNode);
			}else{
				node.getParentNode().setRightNode(lowerNode);
			}
			
			lowerNode.setLeftNode(node);
			node.setParentNode(lowerNode);
		}
	}
	
	private void rotateRight(RedBlackTreeNode<E> node){
		if(node != null){
			RedBlackTreeNode<E> upperNode = (RedBlackTreeNode<E>) node.getLeftNode();
			node.setLeftNode(upperNode.getRightNode());
			
			if(upperNode.getRightNode() != null){
				upperNode.getRightNode().setParentNode(node);
			}
			upperNode.setParentNode(node.getParentNode());
			
			if(node.getParentNode() == null){
				root = upperNode;
			}else if(node == node.getParentNode().getRightNode()){
				node.getParentNode().setRightNode(upperNode);
			}else{
				node.getParentNode().setLeftNode(upperNode);
			}
			upperNode.setRightNode(node);
			node.setParentNode(upperNode);
		}
	}
	
	private static <E extends Comparable<E>> RedBlackTreeNode<E> leftOf(RedBlackTreeNode<E> node){
		return node == null ? null : (RedBlackTreeNode<E>) node.getLeftNode();
	}
	
	private static <E extends Comparable<E>> RedBlackTreeNode<E> rightOf(RedBlackTreeNode<E> node){
		return node == null ? null : (RedBlackTreeNode<E>) node.getRightNode();
	}
	
	private static <E extends Comparable<E>> RedBlackTreeNode<E> parentOf(RedBlackTreeNode<E> node){
		return node == null ? null : (RedBlackTreeNode<E>) node.getParentNode();
	}
	
	private static <E extends Comparable<E>> boolean colorOf(RedBlackTreeNode<E> node){
		return node == null ? BLACK : node.getNodeColor();
	}
}
